1. Field of the invention
The present invention relates to a code transmission scheme to be used for the purpose of realizing reliable end-to-end communications between networks, especially computers.
2. Description of the Background Art
The computer communication conventionally adopts a scheme in which data are sequentially transferred between small sized networks called subnets via devices such as bridges and routers. Here, a data unit for transfer is called an IP (Internet Protocol) packet.
The IP packet transfer has been realized on the best effort basis historically, where it is assumed that data can be discarded or lost at network devices such as switches and routers provided within the network. Then, when an IP packet transmitted from a transmitting side fails to reach a receiving side, in general, either an end-to-end re-transmission has been carried out (by TCP (Transmission Control Protocol), for example), or no action has been taken (by UDP (User Datagram Protocol), for example) even if this communication fails.
Also, conventionally, communications using computers have been predominantly of point-to-point type. However, recently, there is an increasing need for communications using multicast. Conventionally, in the case of realizing multicast, it has been common to adopt a scheme in which UDP and the like is used as the upper level protocol and no request for high quality is allowed. The reason for this is that, if the end-to-end re-transmission control is carried out by utilizing the multicast, a number of ACK (Acknowledgement)/NACK (Negative Acknowledgement) signals for indicating whether the receiving has been successful or not from the receiving side increases in proportion to a number of receiving terminals, so that the processing load at a transmitting terminal can be increased.
In view of such a background, there have been propositions for a scheme using end-to-end error correction as a scheme for realizing both a multicast system and reliable communications.
As a first example, a communication scheme that secures the end-to-end reliability by adding error correction cells using Reed-Solomon (RS) codes to a plurality of ATM cells has been disclosed in Japanese Patent Application Laid Open No. 8-186570 (1996). According to this scheme, the usual Reed-Solomon code is separated into the information section used as ATM cells for data and the redundant section used as ATM cells for codes, so that when m cells for data and one cell for codes are provided, it is possible to recover discarded cells up to one cell among (m+1) cells using the error correction. By such an application of the error correcting codes, it is possible to realize high quality end-to-end communications.
However, this scheme is associated with the following problem. In general, it is preferable to be able to set the level of redundancy individually by a communication network. However, because the usual code words are used currently, it is necessary to carry out different coding calculating processing when the number of redundant cells to be attached is changed.
More specifically, the RS code has the redundant section which is a residue obtained by dividing the information section by a polynomial called G(X). For instance, in the case of using one cell redundancy, G(X) can be expressed as:
G(X)=Xxe2x88x92xcex1bxe2x80x83xe2x80x83(1)
where xcex1 is a root of a primitive polynomial used as a base of this code production, and b is an integer whose value is predetermined between the transmitting side and the receiving side. In other words, G(X) must be shared at the transmitting side and the receiving side. However, in the cases of two cells redundancy and three cells redundancy, G(X) can be expressed respectively as:
G(X)=(Xxe2x88x92xcex1b)(Xxe2x88x92xcex1(b+1))xe2x80x83xe2x80x83(2)
G(X)=(Xxe2x88x92xcex1b)(Xxe2x88x92xcex1(b+1))(Xxe2x88x92xcex1(b+2))xe2x80x83xe2x80x83(3)
In these cases, the respective polynomials have different degrees so that it is necessary to carry out a division calculation separately for each of them. This implies in terms of the hardware implementation that there is a need to provide completely separate calculation circuit for each of them so that it can cause an increase in the circuit size. Also, in terms of the software program, this implies that a separate program must be produced for each of them, so that it can cause an increase in the amount of software programs.
Next, as a second example of a proposition for a scheme using end-to-end error correction, a scheme which is conceived as a technique for combining the error correction and the re-transmission will be described. This scheme is considered particularly effective in the case of multicast.
First, a sender sends m information packets and l redundant packets that are associated with these information packets to a receiver, where l is a 0 or a positive integer. When the receiver detects that l or less packets among (m+1) packets fails to arrive, the correction using the redundant packets is carried out. However, when discarding of lxe2x80x2 packets (lxe2x80x2 greater than l) occurs in the middle, the receiver requests the re-transmission of (lxe2x80x2xe2x88x92l) packets to the sender. In response, the sender newly produces (lxe2x80x2xe2x88x92l) redundant packets and sends them to the receiver. As a result, the receiver obtains lxe2x80x2 redundant packets so that it becomes possible to recover the original information packets by carrying out the error correction with respect to discarding of lxe2x80x2 packets.
In this scheme, the sender is initially capable of producing l redundant packets using the method as explained in the first example, but there is a problem as to how (lxe2x80x2xe2x88x92l) redundant packets are to be produced subsequently. For instance, suppose that the transmission using two packets redundancy with l=2 is carried out initially as in the first example, using G(X) given by:
G(X)=(Xxe2x88x92xcex1b)(Xxe2x88x92xcex1(b+1))xe2x80x83xe2x80x83(4)
and suppose that four packets fail to arrive at the receiving side due to discarding. In such a case, the re-transmission request for remaining two packets will be issued from the receiving side to the transmitting side. In response, the transmitting side is required to produce the redundant packets using, for example, a polynomial given by:
Gxe2x80x2(X)=(Xxe2x88x92xcex1(b+2))(Xxe2x88x92xcex1(b+3))xe2x80x83xe2x80x83(5)
At this point, it is meaningless to use the equation (4) because that would result in the transmission of the same redundant packets, so that it is necessary to use the polynomial like that of the equation (5) which uses different powers of xcex1. Consequently, there is a need to newly produce Gxe2x80x2 (X) according to the number of re-transmission packets requested from the receiving side, and therefore there are problems of an increase in the circuit size and an increase in the amount of software programs similarly as in the first example.
Thus, conventionally, the re-transmission control using a protocol such as TCP has been carried out for data that requires the reliability, but a scheme using the error correction for the purpose of dealing with multicast has appeared. However, in the conventional scheme that transmits the redundant section of the usual error correcting codes as it is, there is a problem that the number of redundant packets cannot be changed flexibly. In addition, even in the case of combining that with the re-transmission control, there is also a problem that the redundant packets cannot be provided flexibly at a time of re-transmission.
It is therefore an object of the present invention to provide a code transmission scheme for a communication system using error correcting codes, which is capable of reducing a circuit size and an amount of software programs without affecting the error correction performance.
It is another object of the present invention to provide a flexible error correction scheme according to a state of communication network.
It is another object of the present invention to provide an error correction scheme which can produce redundant packets easily even in the case of using the re-transmission in combination.
It is another object of the present invention to provide a reliable communication system realizing the multicast, using the error correction scheme of the present invention.
According to one aspect of the present invention there is provided a method for transmitting an error correcting code corresponding to an information to be transmitted in a communication system, comprising the steps of: generating at least one transmitting side syndrome value by carrying out a syndrome calculation for the information to be transmitted at a transmitting side; and transmitting, from the transmitting side to a receiving side, at least one information packet containing the information to be transmitted and at least one redundant packet containing the transmitting side syndrome value generated by the generating step as a redundant part of the error correcting code.
In this aspect of the present invention, the generating step can generate as many transmitting side syndrome values as a number corresponding to a desired error correction capability using said number of mutually different polynomials of degree one.
Conventionally, one redundant part is generated using a polynomial of degree corresponding to the desired error correction capability, but the present invention generates said number of redundant parts using said number of polynomials of degree one, so that when it is desired to increase the error correction capability, it suffices to simply increase the number of mutually different polynomials of degree one and repeat the coding calculation as many times as that number using the common calculation method or circuit configuration, rather than calculating the redundant part using the polynomial of increased degree (which makes the circuit larger and complicated as the different circuit configuration is required for the coding calculation when the degree is changed).
Also, in this aspect of the present invention, the method can further comprise the step of: transmitting another redundant packet containing another transmitting side syndrome value, as re-transmission from the transmitting side to the receiving side, when the receiving side cannot recover the information from the information packet and the redundant packet received by the receiving step.
In the case of re-transmission, it suffices to generate and transmit as many redundant parts as necessary for the recovery of the information (or more) using that many of the polynomials of degree one (which are different from those used at a time of initial transmission), so that the coding calculation can be carried out using the common calculation method or circuit configuration both at a time of initial transmission and at a time of re-transmission. Here, the number of redundant parts to be transmitted at a time of re-transmission may be the number requested from the receiving side. Alternatively, it is also possible to use a scheme in which the transmitting side transmits a prescribed number of redundant parts and each receiving side selectively receives as many as necessary or can be processed at each receiving side. Also, in the case of using multicast, even when the number of redundant parts necessary for the recovery of the information at some receiving side differs from the number of redundant parts necessary for the recovery of the information at another receiving side, there is no need to carry out totally different calculations (using polynomials of different degrees) with respect to these receiving sides as has been required conventionally, and it suffices to generate and transmit the largest number of redundant parts necessary such that some receiving side can recover the information using all of these redundant parts while another receiving side can recover the information using only part of these redundant parts. Here, it is also possible to send all of the plurality of generated redundant parts to some receiving side and only a part of the plurality of generated redundant parts to another receiving side.
Also, in this aspect of the present invention, the transmitting step can transmit the information packet and the redundant packet by multicast with respect to a plurality of receiving sides.
In the case of multicast, even when the error correction capability desired by some receiving side differs from the error correction capability desired by another receiving side, there is no need to carry out totally different calculations (using polynomials of different degrees) with respect to these receiving sides as has been required conventionally, and it suffices to generate some number of redundant parts of the error correcting code using the common calculation method or circuit configuration, transmit them to the receiving sides, and receive and use only as many redundant parts as necessary or can be processed at each receiving side.
According to another aspect of the present invention there is provided a method for transmitting an error correcting code corresponding to an information to be transmitted in a communication system, comprising the steps of: transmitting, from a transmitting side to a receiving side, packets generated by applying an error correction coding processing with respect to the information to be transmitted at the transmitting side; and generating at least one transmitting side syndrome value by carrying out a syndrome calculation for the information to be transmitted at the transmitting side, and transmitting, from the transmitting side to the receiving side, at least one redundant packet containing the transmitting side syndrome value as a redundant part of the error correcting code, when the receiving side cannot recover the information to be transmitted from the packets received from the transmitting side and requests a re-transmission.
It is possible to realize the significant effect by carrying out the transmission using arbitrary error correction coding scheme (which can be even the conventional coding scheme) at a time of transmitting the information first, and then carry out the transmission using the error correction coding scheme of the present invention when a re-transmission is requested. For example, in the case of multicast communication, even when the amount of information necessary for the recovery of the information at some receiving side differs from the amount of information necessary for the recovery of the information at another receiving side, there is no need to carry out totally different calculations (using polynomials of different degrees) with respect to these receiving sides as has been required conventionally, and it suffices to generate some number of redundant parts using the common calculation method or circuit configuration, and re-transmit them to the plurality of receiving sides, such that some receiving side can recover the information using all of these redundant parts while another receiving side can recover the information using only part of these redundant parts.
According to another aspect of the present invention there is provided a transmission device for transmitting an error correcting code corresponding to an information to be transmitted in a communication system, comprising: a generation unit for generating at least one transmitting side syndrome value by carrying out a syndrome calculation for the information to be transmitted at a transmitting side; and a transmission unit for transmitting, from the transmitting side to a receiving side, at least one information packet containing the information to be transmitted and at least one redundant packet containing the transmitting side syndrome value generated by the generation unit as a redundant part of the error correcting code.
According to another aspect of the present invention there is provided a reception device for receiving an error correcting code corresponding to an information to be transmitted in a communication system, comprising: a reception unit for receiving at least a part of at least one information packet containing the information to be transmitted and at least one redundant packet containing at least one transmitting side syndrome value for the information to be transmitted as calculated by a transmitting side; a calculation unit for obtaining at least one receiving side syndrome value by carrying out a syndrome calculation for an information contained in the information packet as received by the reception unit; and a correction unit for performing error correction, if required, by calculating a difference between the transmitting side syndrome value contained in the redundant packet as received by the reception unit and the receiving side syndrome value obtained by the calculation unit.
According to another aspect of the present invention there is provided a communication system for transmitting an error correcting code corresponding to an information to be transmitted, comprising: a generation unit for generating at least one transmitting side syndrome value by carrying out a syndrome calculation for the information to be transmitted at a transmitting side; a transmission unit for transmitting, from the transmitting side to a receiving side, at least one information packet containing the information to be transmitted and at least one redundant packet containing the transmitting side syndrome value generated by the generation unit as a redundant part of the error correcting code; a reception unit for receiving at least a part of the information packet and the redundant packet transmitted by the transmission unit; a calculation unit for obtaining at least one receiving side syndrome value by carrying out a syndrome calculation for an information contained in the information packet as received by the reception unit; and a correction unit for performing error correction, if required, by calculating a difference between the transmitting side syndrome value contained in the redundant packet as received by the reception unit and the receiving side syndrome value obtained by the calculation unit.